class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        int ans = 0;
        heights.push_back(0);
        deque<pair<int, int>> que;
        for (int i = 0; i < heights.size(); i++)
        {
            int num = 0;
            while (!que.empty() && que.back().first >= heights[i])
            {
                ans = max(ans, que.back().first * (que.back().second + num));
                num += que.back().second;
                que.pop_back();
            }
            que.push_back(pair<int, int>(heights[i], num + 1));
        }
        return ans;
    }
};